package algo.sort;

public class Shell <T extends Comparable<? super T>> extends Sort<T>{
    // 希尔排序的思路不太适合我， 间隔序列的思路不易想到
    // 又因为希尔排序效率仍比不上其他的高级排序，我抄了代码就不看了
    @Override
    public void sort(T[] nums) {
        int len = nums.length;
        int h = 1;

        while (h < len / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            for (int i=h; i<len; ++i) {
                for (int j=i; j>=h && less(nums[j], nums[j-h]); j -= h) {
                    swap(nums, j, j-h);
                }
            }
            h = h / 3;
        }
    }

    @Override
    public void sortDesc(T[] nums) {
        int len = nums.length;
        int h = 1;

        while (h < len / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            for (int i=h; i<len; ++i) {
                for (int j=i; j>=h && greater(nums[j], nums[j-h]); j -= h) {
                    swap(nums, j, j-h);
                }
            }
            h = h / 3;
        }
    }
}
